package leetcode;

public class MaxAreaIsland {
    public static void main(String[] args) {
        System.out.println(maxAreaOfIsland(new int[][] {{0,0,1,0,0,0,0,1,0,0,0,0,0},{0,0,0,0,0,0,0,1,1,1,0,0,0},
                {0,1,1,0,1,0,0,0,0,0,0,0,0},{0,1,0,0,1,1,0,0,1,0,1,0,0},{0,1,0,0,1,1,0,0,1,1,1,0,0},
                {0,0,0,0,0,0,0,0,0,0,1,0,0},{0,0,0,0,0,0,0,1,1,1,0,0,0},{0,0,0,0,0,0,0,1,1,0,0,0,0}}));
        System.out.println(maxAreaOfIsland(new int[][] {{1,1,0,0,0},{1,1,0,0,0},{0,0,0,1,1},{0,0,0,1,1}}));
    }
    public static int maxAreaOfIsland(int[][] grid) {
        int result = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == 1)
                    result = Math.max(result, bfs(i, j, grid));
            }
        }
        return result;
    }
    public static int bfs(int i, int j,  int[][] grid){
        if(i  < 0 || j  < 0 || i  >= grid.length || j  >= grid[0].length || grid[i][j] == 0 || grid[i][j] == 2)
            return 0;
        grid[i][j] = 2;
        return 1 + bfs(i - 1, j, grid) + bfs(i, j - 1, grid) +  bfs(i + 1, j, grid) + bfs(i, j + 1, grid);
    }
}
/*
{{0,0,1,0,0,0,0,1,0,0,0,0,0},{0,0,0,0,0,0,0,1,1,1,0,0,0},{0,1,1,0,1,0,0,0,0,0,0,0,0},
{0,1,0,0,1,1,0,0,1,0,1,0,0},{0,1,0,0,1,1,0,0,1,1,1,0,0},{0,0,0,0,0,0,0,0,0,0,1,0,0},
{0,0,0,0,0,0,0,1,1,1,0,0,0},{0,0,0,0,0,0,0,1,1,0,0,0,0}}
 */
/*
{{1,1,0,0,0},{1,1,0,0,0},{0,0,0,1,1},{0,0,0,1,1}}
 */
